package com.gitee.feizns.explore.data_structure.linked_list.singly.odd;

/**
 * 奇偶链表
 * 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
 *
 * 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
 * @author feizns
 * @since 2019/9/30
 */
public class Odd {

    public static void main(String[] args) {
        ListNode node = create();
        node.print();
        oddEvenList(node).print();
    }

    public static ListNode oddEvenList(ListNode head) {
        if ( head == null || head.next == null )
            return head;

        ListNode oddLast = head;
        ListNode even = head.next;
        ListNode evenLast = even;
        while ( evenLast != null && evenLast.next != null ) {
            oddLast.next = evenLast.next;
            oddLast = oddLast.next;
            evenLast.next = oddLast.next;
            evenLast = evenLast.next;
        }
        oddLast.next = even;
        return head;
    }
//
//    public static ListNode oddEvenList2(ListNode head) {
//        if (head == null || head.next == null || head.next.next == null) {
//            return head;
//        }
//        ListNode odd = new ListNode(-1);
//        ListNode oddHead = odd;
//        ListNode even = new ListNode(-1);
//        ListNode evenHead = even;
//        while (head != null && head.next != null) {
//            odd.next = head;
//            even.next = head.next;
//            odd = odd.next;
//            even = even.next;
//            head = head.next.next;
//        }
//        //防止最后还有一个节点
//        if (head != null) {
//            odd.next = head;
//            odd = odd.next;
//            even.next = null;
//        }
//        odd.next = evenHead.next;
//        return oddHead.next;
//    }

//    public static ListNode oddEvenList(ListNode head) {
//        if ( head == null ) return null;
//
//        ListNode odd = null;
//        ListNode oddLast = null;
//        ListNode even = null;
//        ListNode evenLast = null;
////        ListNode curt = head;
//
//        for (int i = 1; head != null; i++) {
//            if ( i % 2 != 0 ) {
//                if ( odd == null )
//                    odd = oddLast = head;
//                else {
//                    oddLast.next = head;
//                    oddLast = oddLast.next;
//                }
//            } else {
//                if ( even == null )
//                    even = evenLast = head;
//                else {
//                    evenLast.next = head;
//                    evenLast = evenLast.next;
//                }
//            }
//            head = head.next;
//        }
//        oddLast.next = even;
//        return odd;
//    }

    private static ListNode create() {
        ListNode node = new ListNode(0);
        node.next = new ListNode(1);
        node.next.next = new ListNode(2);
        node.next.next.next = new ListNode(3);
        node.next.next.next.next = new ListNode(4);
        node.next.next.next.next.next = new ListNode(5);
        return node;
    }

}
